package day_2022_12_to_3.year2023;

import java.util.HashMap;
import java.util.Map;

/**
 * @author haomin
 * @date 2023/01/20 22:51
 **/

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

public class Day1_20_Review {
    class Solution35 {
        public Node copyRandomList(Node head) {
            Map<Node, Node> map = new HashMap<>();
            Node cur = head;
            while(cur != null) {
                map.put(cur, new Node(cur.val));
                cur = cur.next;
            }
            cur = head;
            while(cur != null) {
                map.get(cur).next = map.get(cur.next);
                map.get(cur).random = map.get(cur.random);
                cur = cur.next;
            }
            return map.get(head);
        }
    }



    class Solution36 {
        class Node {
            public int val;
            public Node left;
            public Node right;

            public Node() {}

            public Node(int _val) {
                val = _val;
            }

            public Node(int _val,Node _left,Node _right) {
                val = _val;
                left = _left;
                right = _right;
            }
        }

        Node head, pre;
        public Node treeToDoublyList(Node root) {
            if(root == null) return null;
            inorder(root);
            pre.right = head;
            head.left = pre;
            return head;
        }
        public void inorder(Node root) {
            if(root == null) return;
            inorder(root.left);
            if(head == null) head = root;
            else {
                pre.right = root;
                root.left = pre;
            }
            pre = root;
            inorder(root.right);
        }
    }
}